package primary.design;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.
 * @Author Elephas
 * @Date 2022/1/9
 **/
public interface ShuffleArray {
    int[] reset();
    int[] shuffle();
}

/**
 * 实现思路：对于一个给定的数组，计算其所有全排列，并存储，全排列初始化时的时间为o(n!)，查询时从其全排列中取出一个，时间为o(1)
 */
class ShuffleArrayImpl1 implements ShuffleArray{
    private List<int[]> permutations = null;
    private int[] originalNums;
    public ShuffleArrayImpl1(int[] nums) {
        this.originalNums = nums;
        initPermutations();
    }

    private void initPermutations(){
        this.permutations = new ArrayList<>();
        int[] stack = new int[this.originalNums.length];
        boolean[] isVisited = new boolean[this.originalNums.length];
        for (int i = 0; i < isVisited.length; i++) {
            isVisited[i] = false;
        }
        int top = 0;

        traceBack(stack,top,isVisited);
    }

    private void traceBack(int[] stack,int top,boolean[] isVisited){
        if(top == stack.length){
            int[] permutation = new int[stack.length];
            for (int i = 0; i < stack.length; i++) {
                permutation[i] = stack[i];
            }
            permutations.add(permutation);
        }else{
            for (int i = 0; i < this.originalNums.length; i++) {
                if(!isVisited[i]){
                    isVisited[i] = true;
                    stack[top++] = this.originalNums[i];
                    traceBack(stack,top,isVisited);
                    top--;
                    isVisited[i] = false;
                }
            }
        }
    }
    public int[] reset() {
        return this.originalNums.clone();
    }

    public int[] shuffle() {
        return this.permutations.get((int)(Math.random()*this.permutations.size())).clone();
    }
}

/**
 * Fisher–Yates shuffle Algorithm
 * 从最后一次迭代开始，若 随机数 r = n - 1 ，则最后一个元素保持原位，概率为 1/n
 *                 在第一次迭代 r != n - 1 的条件下，最后一个元素与前面 n - 1 个元素中某一个交换了位置， 记该位置为 k
 *                 估计第二次迭代，将第 n - 2 个元素与第 k 个元素交换的概率
 *                 随机数 r roll 到 k 的概率为 1 / (n - 1), 呈上第一次 r 的结果不为 n -1 的概率 (n - 1) / n
 *                 得到在倒数第二个位置的概率为 (1 / (n - 1)) * ((n - 1) / n) = 1 / n
 *                 同理可得最后一个元素在其它位置的概率均为 1 / n
 */
class ShuffleArrayImpl2 implements ShuffleArray{
    private int[] originalNums;
    private Random random;
    public ShuffleArrayImpl2(int[] nums){
        this.originalNums = nums;
        this.random = new Random();
    }
    @Override
    public int[] reset() {
        return this.originalNums.clone();
    }

    @Override
    public int[] shuffle() {
        int[] copy = this.originalNums.clone();
        for (int i = copy.length - 1; i > 0; i--) {
            int r = this.random.nextInt(i + 1);
            int temp = copy[r];
            copy[r] = copy[i];
            copy[i] = temp;
        }
        return copy;
    }
}
